import java.util.Iterator;
import java.util.Random;
import java.util.Vector;


public class SortedLinkedList<T extends Comparable<T>> implements Iterable<T>{
	private class Node<T extends Comparable<T>>{
		public T data;
		public Node<T> next;
		public Node() { this(null); }
		public Node(T data){
			this.data = data;
			next = null;
		}
	}
	public class NodeIterator<T extends Comparable<T>> implements Iterator<T>{
		private Vector<T> v;
		private int current;
		public NodeIterator(Node<T> head){
			v = new Vector<T>();
			while(head != null){
				v.add(head.data);
				head = head.next;
			}
			current = 0;
		}
		public boolean hasNext() {
			return (current < v.size());
		}
		public T next() {
			T elt = v.get(current);
			current++;
			return elt;
		}
		public void remove() {
			
		}
	}
	
	private Node<T> head;
	int count;
	
	SortedLinkedList(){
		head = null;
		count = 0;
	}
	
	
	SortedLinkedList(T element){
		head = new Node(element);
		count = 0;
	}
	
	public int size(){
		return count;
	}
	public boolean add(T element){
		if(head == null){
			head = new Node<T>(element);
			count++;
			return true;
		} else if(element.compareTo(head.data) <= 0) {
			Node newNode = new Node(element);
			newNode.next = head;
			head = newNode;
			count++;
			return true;
		} else {
			Node temp = head;
			while(temp.next != null && temp.next.data.compareTo(element) < 0){
				temp = temp.next;
			}
			Node newNode = new Node(element);
			newNode.next = temp.next;
			temp.next = newNode;
			count++;
			return true;
		}
	}
	
	public boolean remove(T element){
		if(head == null){
			return false;
		} else if(head.data.equals(element)){	
			head = head.next;
			count--;
			return true;
		} else {
			Node temp = head;
			while(temp.next != null && !temp.next.data.equals(element)){
				temp = temp.next;
			}
			if(temp.next == null){
				return false;
			} else {	
				temp.next = temp.next.next;
				count--;
				return true;
			}
				
		}
	}
	
	public boolean contains(T element){
		if(head == null){
			return false;
		} else if (head.data.equals(element)){	
			return true;
		} else {
			Node temp = head;
			while(temp.next != null && temp.next.data.equals(element)){
				temp = temp.next;
			}
			if(temp.next == null){
				return false;
			} else {
				return true;
			}				
		}
	}
	
	public boolean isEmpty(){
		if(count == 0){
			return true;
		} else {
			return false;
		}
	}	
	
	@SuppressWarnings("unchecked")
	public T get(int index) throws IndexOutOfBoundsException{
		if(count == 0){
			throw new IndexOutOfBoundsException();
		} else {
			Node temp = head;
			int i = 0;
			while(temp.next != null && i < index){
				temp = temp.next;
				i++;
			}
			if(temp.next == null){
				throw new IndexOutOfBoundsException();
			} else {
				return (T) temp.data;
			}
		}
	}
	
	@SuppressWarnings("unchecked")
	public T set(int index, T element) throws IndexOutOfBoundsException {
		if(count == 0){
			throw new IndexOutOfBoundsException();
		} else {
			Node temp = head;
			int i = 0;
			while(temp.next != null & i < index){
				temp = temp.next;
				i++;
			}
			if(temp.next == null){
				throw new IndexOutOfBoundsException();
			} else {
				T oldData = (T)temp.data;
				temp.data = element;
				return oldData;
			}
		}
	}
	
	public Iterator<T> iterator(){
		return new NodeIterator<T>(head);
	}
	
	public String toString(){
		String s = "";
		Node temp = head;
		for(int i = 0; i < count; i++){
			s += String.valueOf(temp.data) + " <- ";
			temp = temp.next;
		}
		s += "null";
		return s;
	}

	
	/**
	public static void main(String[] args){
		SortedLinkedList<Integer> f = new SortedLinkedList<Integer>();
		Random r = new Random();
		for(int i = 0; i < 35; i ++){
			f.add(r.nextInt(100));
		}
		System.out.println(f);
		for(Integer e : f){
			System.out.println(e);
		}
	}
	*/
	
}
